# 226. 翻转二叉树
# 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
#
# 示例 1：
# 输入：root = [4,2,7,1,3,6,9]
# 输出：[4,7,2,9,6,3,1]
#
# 示例 2：
# 输入：root = [2,1,3]
# 输出：[2,3,1]
# 示例 3：
#
# 输入：root = []
# 输出：[]


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def invertTree(self, root):
        if not root:
            return root
        from collections import deque
        que = deque()
        que.append(root)
        while que:
            size = len(que)
            for i in range(size):
                cur = que.popleft()
                cur.left, cur.right = cur.right, cur.left
                # 这里出了问题，需要判断不为空才加，一开始没想明白
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
                # if cur.left and cur.right:
                #     cur.left, cur.right = cur.right, cur.left
                #     que.append(cur.left)
                #     que.append(cur.right)
                # elif cur.left:
                #     cur.right = cur.left
                #     que.append(cur.right)
                # else:
                #     cur.left = cur.right
                #     que.append(cur.left)
        return root

    def invertTree2(self, root): # 递归
        if not root:
            return root
        def rever(root):
            if not root:
                return
            root.left, root.right = root.right, root.left
            rever(root.left)
            rever(root.right)
        rever(root)
        return root

    def invertTree3(self, root): # 迭代
        if not root:
            return root
        stack = []
        stack.append(root)
        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return root



if __name__ == '__main__':
    a31 = TreeNode(15)
    a32 = TreeNode(7)
    a21 = TreeNode(9)
    a22 = TreeNode(20, a31, a32)
    a11 = TreeNode(3, a21, a22)
    tmp = Solution()
    # res = tmp.invertTree2(a11)
    res = tmp.invertTree3(a11)
    print(res.val)
    print(res.val)